package alo.p3.work;

import alo.p3.ListNode;

import java.util.ArrayList;


/*
* 给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
*/
public class partition {

    class Solution {
        public ListNode partition(ListNode head, int x) {
            ArrayList<ListNode> list1=new ArrayList<>();
            ArrayList<ListNode> list2=new ArrayList<>();
            ListNode c1=head,c2;
            while (c1!=null){
                if (c1.getData()<x){
                    list1.add(c1);
                }else list2.add(c1);
                c1=c1.getNext();
            }
            if (!list1.isEmpty()) {
                head=list1.get(0);
                c1 =head;
                for (int i = 1; i < list1.size(); i++) {
                    c1.setNext(list1.get(i));
                    c1 = c1.getNext();

                }
            }else return head;
            if(!list2.isEmpty()) {
                c2 = list2.get(0);
                c1.setNext(c2);
                for (int i = 1; i < list2.size(); i++) {
                    c2.setNext(list2.get(i));
                    c2 = c2.getNext();
                }
                c2.setNext(null);
                return head;
            }else {
                c1.setNext(null);
                return head;
            }
        }
    }
    class Solution2 {
        public ListNode partition(ListNode head, int x) {


            ListNode before_head = new ListNode(0);
            ListNode before = before_head;
            ListNode after_head = new ListNode(0);
            ListNode after = after_head;

            while (head != null) {

                if (head.getData() < x) {
                    before.setNext(head);
                    before = before.getNext();
                } else {
                    after.setNext(head);
                    after = after.getNext();
                }

                head = head.getNext();
            }

            after.setNext(null);

            before.setNext(after_head.getNext());

            return before_head.getNext();
        }
    }
}
